package practiceTest.chap03.work3.InsertSort;

/**
 * Created by root on 2017/7/12.
 */
public class ArrayIns
{
    private long[] a;                 // ref to array a
    private int nElems;               // number of data items
    //--------------------------------------------------------------
    public ArrayIns(int max)          // constructor
    {
        a = new long[max];                 // create the array
        nElems = 0;                        // no items yet
    }
    //--------------------------------------------------------------
    public void insert(long value)    // put element into array
    {
        a[nElems] = value;             // insert it
        nElems++;                      // increment size
    }
    //--------------------------------------------------------------
    public void display()             // displays array contents
    {
        for(int j=0; j<nElems; j++)       // for each element,
            System.out.print(a[j] + " ");  // display it
        System.out.println("");
    }
    //--------------------------------------------------------------

    /**
     * 插入排序用for和while都能循环，while更适合在某种情况下终止循环，
     * for适合在某个范围内循环，所以while更适合插入循序
     */

    public void InsertSort() {
        int out,in;
        long temp;
        for (out=1; out<nElems; out++) {
            temp = a[out];
            for (in=out; in>0; in--) {
                if (a[in-1] > temp) {
                    a[in] = a[in-1];
                } else {
                    break;
                }
            }
            a[in] = temp;
        }
    }
    public void InsertSortWhile() {
        int out,in;
        long temp;
        for (out=1; out<nElems; out++) {
            temp = a[out];
            in = out;
            while (in>0 && a[in-1] > temp) {
                a[in] = a[in-1];
                in--;
            }
            a[in] = temp;
        }
    }
    //--------------------------------------------------------------
    private void swap(int one, int two)
    {
        long temp = a[one];
        a[one] = a[two];
        a[two] = temp;
    }

    public void noDups2(){
        int in,out;
        int k=0;
        for (out=0; out<nElems-1; out++){
            for (in=out+1; in<nElems; in++) {
                if (a[out] == a[in] && a[out]!=-1){
                    a[in] = -1;
                    k++;
                }
            }
        }

        for (int i=0;i<nElems;i++) {
            if (a[i] == -1) {
                int j=i+1;
                while (a[j]==-1){
                    j++;
                }
                a[i] = a[j];
                a[j] = -1;
            }
        }
        nElems = nElems - k;
    }

    /**
     * 思想：空洞后的
     */
    public void noDups3(){
    int in,out;
    int holenumber = 0;
    final int FLAG = -1;
    for (out=0; out<nElems-1; out++){
        for (in=out+1; in<nElems; in++) {
            if (a[out] == a[in] && a[out] != FLAG){
                a[in] = FLAG;
                holenumber++;
            }
        }
    }

    int firsthole = -1;//第一个空位的索引
    for (int i=0; i<nElems; i++) {
        if (a[i] == FLAG && firsthole == -1) {
            firsthole = i;
        } else if (a[i] != FLAG && firsthole != -1) {
            a[firsthole++] = a[i];
        }
    }

    nElems = nElems - holenumber;
}

    /**
     * 在有序数组中，判断重复只需比较前后位置的数就行
     */
    public void noDups4(){
        long NIL = Long.MIN_VALUE; // 标志位
        for (int i = 0; i < nElems - 1; i++) {
            if (a[i] == a[i + 1]) {
                a[i] = NIL; // NIL为标志位，相当于楼主的-1，使用的是Long.MIN_VALUE
            }
        }
        int order = 0;
        for (int temp = 0; temp < nElems;) {
            if (a[temp] != NIL) {// 因为a[0]不可能等于NIL所以才可以用这种方法
                if (temp > order) {
                    a[order] = a[temp];
                }
                temp++;
                order++;
            } else
                temp++;
        }
        nElems = order;
    }
//--------------------------------------------------------------
}  // end class ArrayBub
